/*
 * Implementation of Preflow Push algorithm for Max Flow of
 * a Flow Network problem.
 * 
 * Author: William Kim
 * Winter 2013
 */

package netflow;

import java.util.Hashtable;
import java.util.LinkedList;

/**
 * Class for solving the Max Flow on a Flow Network Problem using the
 * Preflow-Push method.
 * 
 * The Vertex's name field stores a String identifier and the data field is used
 * for storing height. The Edge's name field is unused (null) and data field
 * stores capacity.
 * 
 * 
 */
public final class PreflowPush
{
  private SimpleGraph flowNetwork;
  private LinkedList<Vertex> excessVertices;
  private int n, m;
  private Hashtable<Vertex, Integer> excess;
  private Hashtable<Edge, Integer> flow;
  private Vertex s = null, t = null;

  public PreflowPush(final SimpleGraph theFlowNetwork)
  {
    flowNetwork = theFlowNetwork;
    excessVertices = new LinkedList<Vertex>();
    n = flowNetwork.numVertices();
    m = flowNetwork.numEdges();
    excess = new Hashtable<Vertex, Integer>(n);
    flow = new Hashtable<Edge, Integer>(m);
  }

  public int maxFlow()
  {
    initialize();
    int maxFlow = 0;

    while (!excessVertices.isEmpty())
    {
      Vertex v = excessVertices.getLast();
      if (excess.get(v) == 0)
      {
        excessVertices.removeLast();
      } else
      {
        pushRelabel(v);
      }
    }

    for (Object edge : s.incidentEdgeList)
    {
      Edge e = (Edge) edge;
      maxFlow += flow.get(e);
    }
    return maxFlow;
  }

  /**
   * Set up the initial conditions of the Preflow before beginning to push flow.
   * Also includes the first saturating push out to all edges out of s.
   */
  private void initialize()
  {
    boolean sfound = false, tfound = false;

    for (Object vertex : flowNetwork.vertexList)
    {
      Vertex v = (Vertex) vertex;
      v.setData(0);
      excess.put(v, 0);

      if (!sfound && v.getName().equals("s"))
      {
        s = v;
        s.setData(n);
        sfound = true;
      } else if (!tfound && v.getName().equals("t"))
      {
        t = v;
        tfound = true;
      }
    }
    for (Object edge : flowNetwork.edgeList)
    {
      Edge e = (Edge) edge;
      flow.put(e, 0);

      if (e.getFirstEndpoint().equals(s))
      {
        updateFlow(e, ((int) (double) e.getData()));
      }
    }
  }

  /**
   * Attempts to push flow. If no eligible push is available, then relabeling
   * occurs. Applicable if e_f(v) > 0, h(w) < h(v) and (v,w) in E_f
   */
  private void pushRelabel(final Vertex v)
  {
    for (Object edge : v.incidentEdgeList)
    {
      Edge e = (Edge) edge;
      Vertex w = flowNetwork.opposite(v, e);
      if ((int) v.getData() > (int) w.getData()) // h(v) > h(w)
      {
        int f_e = flow.get(e);
        int e_v = excess.get(v);
        if (v.equals(e.getSecondEndpoint()) && f_e != 0) // backward edge exists
        {
          updateFlow(e, f_e - Math.min(e_v, f_e));
          break;
        } else if (v.equals(e.getFirstEndpoint()) && ((int) (double) e.getData() - f_e) > 0)
        { // forward edge exists
          updateFlow(e, f_e + Math.min(e_v, (int) (double) e.getData() - f_e));
          break;
        }
      }
    }

    // If it gets to this point, then no eligible push has been found, therefore
    // apply relabel.
    v.setData((int) v.getData() + 1); // Increase h(v) by 1
  }

  private void updateFlow(final Edge edge, final int newF)
  {
    Vertex v = edge.getFirstEndpoint();
    Vertex w = edge.getSecondEndpoint();
    int delta = newF - flow.get(edge);

    flow.put(edge, newF);

    int oldExcessOnV = excess.get(v);
    int oldExcessOnW = excess.get(w);

    excess.put(v, oldExcessOnV - delta);

    if (v != s && v != t && excess.get(v) > 0)
    {
      excessVertices.add(v);
    }

    excess.put(w, oldExcessOnW + delta);
    if (w != s && w != t && excess.get(w) > 0)
    {
      excessVertices.add(w);
    }

  }

  public static void main(final String[] args)
  {
    String test1 = "src/netflow/fixedDegree2/20v-3out-4min-355max.txt";
    String test2 = "src/netflow/fixedDegree2/100v-5out-25min-200max.txt";
    String test3 = "src/netflow/bipartiteGraph/g1.txt";
    String test4 = "src/netflow/bipartiteGraph/g2.txt";
    String test5 = "src/netflow/meshGenerator/smallMesh.txt";
    String test6 = "src/netflow/meshGenerator/mediumMesh.txt";
    String test7 = "src/netflow/random/n10-m10-cmin5-cmax10-f30.txt";
    String test8 = "src/netflow/random/n100-m100-cmin10-cmax20-f949.txt";
    SimpleGraph g = new SimpleGraph();
    GraphInput.LoadSimpleGraph(g, test8);

    PreflowPush pfp = new PreflowPush(g);
    System.out.println(pfp.maxFlow());
  }
}
